package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 翻转二叉树以匹配先序遍历
 */

public class Code971 {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3};
        int[] nums = {1, 3, 2};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code971().flipMatchVoyage(root, nums));
    }

    private int index = 0;
    private List<Integer> ans = new ArrayList<>();
    private int[] voyage;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        boolean success = dfs(root);
        if (success) {
            return ans;
        }

        return Arrays.asList(-1);
    }

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        // 当前节点值是否匹配
        if (index >= voyage.length || node.val != voyage[index]) {
            return false;
        }

        index++; // 匹配成功，移动指针

        // 尝试匹配左子树
        if (node.left != null && index < voyage.length && node.left.val != voyage[index]) {
            // 不匹配，尝试翻转
            ans.add(node.val);
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }

        // 继续递归匹配
        return dfs(node.left) && dfs(node.right);
    }
}
